Grokking Algorithm Complexity and Big-O
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Course Overview
Basics of Algorithm Analysis
Introduction to Algorithm Analysis
Measuring Efficiency
Functions and Their Growth Rates
Asymptotic Notations
Overview of Asymptotic Analysis
Big-O Notation (O-notation)
Big-Omega Notation (Ω-notation)
Big-Theta Notation (Θ-notation)
Little-o and Little-omega Notations
Comparing Asymptotic Notations
Time Complexity Analysis
Understanding Time Complexity
Analyzing Control Structures
Analyzing Simple Algorithms
Best, Worst, and Average Cases
Constant Time: O(1)
Linear Time: O(n)
Quadratic Time: O(n²)
Quiz
Space Complexity Analysis
Understanding Space Complexity
Analyzing Space Complexity of Algorithms
Constant Space: O(1)
Linear Space: O(n)
Quadratic Space: O(n²)
Quiz
Analyzing Recursive Algorithms
Introduction to Recursion
Recursion Tree Method
Recurrence Relation Method
Master Theorem Method
Space Complexity Analysis of Recursive Algorithm
Logarithmic Time and Space: O(log n)
Linearithmic Time: O(n log n)
Exponential Time and Space: O(2ⁿ)
Quiz
Array
Linked List
Hash Table and Set
Stack and Queue
Binary Search Tree
Quiz
Sorting Algorithms
Graph Algorithms
Dynamic Programming Algorithms
Coding Interview Problems
Trade-offs in Algorithm Design
Master Theorem Method

The Master Theorem is a formula that provides a shortcut to solve recurrence relations, specifically those that arise in recursive algorithms that divide a problem into smaller, equally sized subproblems. Instead of expanding and summing up each level of the recursion, the Master Theorem allows us to calculate the time complexity directly from the recurrence relation.

Applicable Problems for the Master Theorem

The Master Theorem is applicable to recurrence relations of the following form:

Where:

  • : The number of subproblems generated at each level.
  • : The factor by which the problem size is divided in each recursive call.
  • : The work done outside the recursive calls (usually at each level of recursion).

When to Use the Master Theorem

The Master Theorem is ideal for analyzing algorithms that:

  1. Divide Problems Equally: The problem size is divided into equal parts in each recursive call (like in merge sort or binary search).
  2. Have Uniform Work per Level: The work done at each level, represented by , follows a standard form (e.g., polynomial).

When Not to Use It

The Master Theorem does not apply if:

  • The subproblems are of unequal size.
  • The recurrence does not match the required form or has irregular work at different levels.

Master Theorem Cases

The Master Theorem defines three cases based on the relationship between and . Each case provides a different time complexity.

  1. Case 1: for some

    • Meaning: The function grows slower than .
    • Result: The total complexity is dominated by the work done at the leaf nodes of the recursion tree.
    • Complexity:
  2. Case 2:

    • Meaning: The function grows at the same rate as .
    • Result: The work is evenly balanced across levels of the recursion tree.
    • Complexity:
  3. Case 3: for some

    • Meaning: The function grows faster than .
    • Condition: If for some constant and sufficiently large , then we can apply this case.
    • Result: The work done at the root dominates the total complexity.
    • Complexity:

Example: Analyzing Merge Sort with the Master Theorem

Merge sort is a classic divide-and-conquer algorithm that sorts an array by splitting it into two halves, sorting each half, and then merging them. Let’s analyze its time complexity using the Master Theorem.

Java
Saved to Cloud

. . . .

Merge Sort Recurrence Relation

The recurrence relation for merge sort is:

  • : Each level generates two subproblems.
  • : The input size is halved at each recursive level.
  • : Merging two halves requires linear work.

Applying the Master Theorem

  1. Calculate :

  1. Identify the Case:

    • Since matches , this corresponds to Case 2.
  2. Result for Case 2:

Thus, the time complexity for merge sort is .

Summary of the Master Theorem

CaseConditionComplexity
Case 1
Case 2
Case 3
Recurrence Relation Method
Space Complexity Analysis of Recursive Algorithm
Mark as Completed

On this page

Applicable Problems for the Master Theorem

When to Use the Master Theorem

When Not to Use It

Master Theorem Cases

Example: Analyzing Merge Sort with the Master Theorem

Summary of the Master Theorem